import java.util.Arrays;

public class LeetCode338 {
    public static void main(String[] args) {
        //比特位计数
        //https://leetcode.cn/problems/counting-bits/solutions/7882/hen-qing-xi-de-si-lu-by-duadua/
        Solution338 s = new Solution338();
        System.out.println(Arrays.toString(s.countBits(2)));
    }
}
class Solution338 {
    public int[] countBits(int n) {
        int[] res = new int[n+1];
        res[0] = 0;
        for(int i = 1; i <= n ; i++){
            //
            if((i%2)!=0){
                res[i] = res[i-1]+1;
            }else{
                res[i] = res[i/2];
            }
        }
        return res;
    }
}